import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 21:32
 * @description Bellman-Ford
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] fli = {{0, 1, 1}, {0, 2, 5}, {1, 2, 1}, {2, 3, 1}};
        solution.findCheapestPrice(4, fli, 0, 3, 1);
    }


    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] dist = new int[n];
        int INF = Integer.MAX_VALUE / 2;
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int limit = 0; limit < k + 1; limit++) {
            int[] clone = dist.clone();
            for (int[] f : flights) {
                int x = f[0], y = f[1], w = f[2];
                dist[y] = Math.min(dist[y], clone[x] + w);
            }
        }
        return dist[dst] > INF / 2 ? -1 : dist[dst];
    }

}
